import java.io.*;
import java.util.*;

public class FlightFinder extends Graph {
	HashMap verticesHash;
	static final int INF = java.lang.Integer.MAX_VALUE;
	
	FlightFinder(){
		super();
		verticesHash = new HashMap();
	}
	public void addVertex(Airport a){
		vertices.add(a);
		verticesHash.put(a.name, a);
	}
	public HashMap computeShortestRoutes(String originCode, int arrivalIntTime, boolean am){
		////////////////////        initialization    //////////////////////
			//make arrivalTime
		GMTtime arrivalTime = new GMTtime(arrivalIntTime, ((Airport)verticesHash.get(originCode)).getOffset(), am);
		
			//create data structures for finding minima
		HashMap timeTrackers = new HashMap();
		BinaryHeap timeHeap = new BinaryHeap();
		for(int i=0; i<vertices.size(); i++){
			timeTrackers.put(((Vertex)vertices.get(i)).getName(),
					timeHeap.insert(INF, (Airport)vertices.get(i)) );
		}
		
			//create data structures for holding minima
		HashMap earliestFlight = new HashMap();
			//key - airportCode, data - previousFlight
		
			//set time to start point
		((BinaryHeap.Tracker)timeTrackers.get(originCode)
				).decreaseKey(
						arrivalTime.getgmtInMinutes());
		
		/////////////////////    Find Minima  ////////////////////////////
		while(!timeHeap.isEmpty()){
			Airport currentAirport = (Airport)timeHeap.extractMinData();
			//System.out.println("Closest airport "+currentAirport.simpleToString());
			Iterator edgesIt = currentAirport.outEdges();
			while(edgesIt.hasNext()){
				Flight activeFlight = (Flight)edgesIt.next();
				Airport activeAirport = (Airport)activeFlight.tail;
					//test to see if airport earliest possibility already obtained
				if(((BinaryHeap.Tracker)timeTrackers.get(activeAirport.getName())).getItem() != null){
						//test to see if catchable
					if(	( ((Flight)earliestFlight.get(currentAirport.getName())) == null && arrivalTime.getgmtInMinutes() + 60 < activeFlight.getDeparture().getgmtInMinutes())
							|| ((Flight)earliestFlight.get(currentAirport.getName())) != null
							&& ((Flight)earliestFlight.get(currentAirport.getName())).getArrival().getgmtInMinutes()
							+ 60
							< activeFlight.getDeparture().getgmtInMinutes() ){
						//System.out.println("  Flight Catchable: "+activeFlight);
						
						int activeArrivalIntTime = activeFlight.getArrival().getgmtInMinutes();
						if(activeArrivalIntTime <= arrivalTime.getgmtInMinutes())
							activeArrivalIntTime += 60*24;
							//test to see if flight better
						if( (((Flight)earliestFlight.get(activeAirport.getName())) == null)
								|| (((Flight)earliestFlight.get(activeAirport.getName())).getArrival().getgmtInMinutes()
										> activeArrivalIntTime)){
								//prevents day transition from giving an incorrect value of the earliest flight
							//System.out.println("    Flight beats current time, updating");
							earliestFlight.put(activeAirport.getName(), activeFlight);
							((BinaryHeap.Tracker)timeTrackers.get(activeAirport.getName())).decreaseKey(activeFlight.getArrival().getgmtInMinutes());
							
						}	
					}
				}
			}
		}
		
		return earliestFlight;
	}
	
	public static String shortestToString(HashMap shortestMap, String destination, GMTtime startTime){
		Flight currentFlight = null;
		Flight previousFlight;
		String currentAirport = destination;
		String itinerary = "";
		do {
			previousFlight = currentFlight;
			currentFlight = (Flight)shortestMap.get(currentAirport);
			if(currentFlight != null)
				currentAirport = currentFlight.getHead().getName();
			if(previousFlight !=null)
				itinerary = "\n"+previousFlight + itinerary;
		}while(currentFlight != null);
		
		String result = "From "+previousFlight.getHead().getName()+" to "+destination+":";
		int minutesTotal = ((Flight)shortestMap.get(destination)).getArrival().minutesSince(startTime);
		int minutes = minutesTotal % 60;
		int hours = (minutesTotal-minutes)/60;
		result += "\nTotal Time is "+hours+" hours and "+minutes+" minutes.";
		return result + itinerary;
		
	}
	
	
	public boolean readFlights(String file){
		Graph g = this;
		HashMap airports = verticesHash;
		BufferedReader r;
		try {
			InputStream is = new FileInputStream(file);
			r = new BufferedReader(new InputStreamReader(is));
		}
		catch (IOException e) {
			System.out.println("IOException while opening flight-data\n" + e);
			return false;
		}
		try {
			boolean stop = false;
			while (!stop){
				String nextline = r.readLine();
				if (nextline == null || nextline.trim().equals("")) // end of file or an empty line
					stop = true;
				else {
					StringTokenizer st = new StringTokenizer(nextline);
					String airline = st.nextToken();
					int flightNum = Integer.parseInt(st.nextToken());
					Airport origin = (Airport)verticesHash.get(st.nextToken());
					int localDepartTime = Integer.parseInt(st.nextToken()); 
					boolean Dam = st.nextToken().equals("A");
					Airport destination = (Airport) verticesHash.get(st.nextToken());
					int localArriveTime = Integer.parseInt(st.nextToken());
					boolean Aam = st.nextToken().equals("A");
					
					Flight f = new Flight(origin, destination,
								new GMTtime(localDepartTime, origin.getOffset(), Dam),
								new GMTtime(localArriveTime, destination.getOffset(), Aam),
								airline, flightNum);
					origin.addEdge(f);
				}
			}
		}
		catch (IOException e) {
			System.out.println("IOException while reading sequence from " +
					"flight-data\n" + e);
			return false;
		}
		return true;
	}
	public boolean readAirports(String file){
		BufferedReader r;
	    try {
	    	InputStream is = new FileInputStream(file);
	    	r = new BufferedReader(new InputStreamReader(is));
	    }
	    catch (IOException e) {
	    	System.out.println("IOException while opening airport-data\n" + e);
	    	return false;
	    }
	    try {
	    	String nextline = r.readLine();
	    	StringTokenizer st = new StringTokenizer(nextline);
	    	int numAirports = Integer.parseInt(st.nextToken());
	    		//	 numAirports is the number of airports, use it as needed

	    	for (int i = 0; i < numAirports; i++){
	    		nextline = r.readLine();  int duration;
	    		st = new StringTokenizer(nextline);
	    		String airportCode = st.nextToken();
	    		int gmtConv = Integer.parseInt(st.nextToken());

	    		addVertex(new Airport(airportCode, gmtConv));
	    	}
	    }
	    catch (IOException e) {
	    	System.out.println("IOException while reading sequence from " +
	    			"airport-data\n" + e);
	    	return false;
	    }
	    return true;
	}
		
	public static void main(String[] args) {
		FlightFinder ff = new FlightFinder();
		ff.readAirports("./data/airport-data.txt");
		ff.readFlights("./data/flight-data.txt");
		//System.out.println(ff);

		ff.demo();
	}
	
	public void demo(){
		HashMap shortestRoutes = null;
		String sourceAirport = null;
		GMTtime beginTime = null;
		int choice =0;
		while(choice != 3){
			Terminal.println("Options: Compute Shortest Routes(1), Show Route(2), Exit(3): ");
			choice = Terminal.readInt();
			if(choice == 1){
				Terminal.println("Source Airport Code: ");
				sourceAirport = Terminal.readWord();
				Terminal.println("Arrival Time at Airport: ");
				int time = Terminal.readInt();
				Terminal.println("AM or PM (A or P)");
				String charAm = Terminal.readWord();
				boolean am = charAm.equals("A");
				beginTime = new GMTtime(time, ((Airport)verticesHash.get(sourceAirport)).getOffset(), am);
				shortestRoutes = computeShortestRoutes(sourceAirport, time, am);
			}
			if(choice == 2){
				Terminal.println("Destination Airport Code: ");
				String dest = Terminal.readWord();
				Terminal.println(shortestToString(shortestRoutes, dest,beginTime));
			}
			
		}
		
	}

}
